package leetcode.all;

import java.util.Arrays;
import java.util.HashMap;
import java.util.LinkedList;

class Solution496 {

    public static void main(String[] args) {

        int[] num1 = {2,4};
        int[] num2 = {1,2,3,4};
        System.out.println(Arrays.toString(nextGreaterElement(num1,num2)));
    }

    public static int[] nextGreaterElement(int[] nums1, int[] nums2) {  //m,n,m<=n
        HashMap<Integer,Integer> numAndNext = new HashMap<>();
        //单调栈
        LinkedList<Integer> stack = new LinkedList<>();
        for(int num:nums2){                                      //n
            //新入栈比栈顶大
            while(!stack.isEmpty()&&num>stack.peekLast()){
                //出栈到第一个比num小的数字并把这些出栈的数字附上next
                int pop = stack.removeLast();
                numAndNext.put(pop,num);
            }
            //入栈
            stack.addLast(num);
        }
        //统计
        int[] res = new int[nums1.length];
        for(int i=0;i<nums1.length;i++){                         //m
            res[i] = numAndNext.getOrDefault(nums1[i],-1);
        }
        return res;
    }
}
